package simple;

import data.TreeNode;
import javafx.util.Pair;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/5/23 16:22
 */
public class No107_二叉树的层次遍历II {
    public static void main(String[] args) {
        Solution107 solution107 = new Solution107();
        TreeNode data = new TreeNode(3);
        data.left = new TreeNode(9);
        data.right = new TreeNode(20);
        data.right.left = new TreeNode(15);
        data.right.right = new TreeNode(7);

        List<List<Integer>> list = solution107.levelOrderBottom(data);
        System.out.println();
    }
}

class Solution107 {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        //迭代
        List<List<Integer>> result = new ArrayList<>();
        List<List<Integer>> reverse = new ArrayList<>();
        levelOrderBottom(root, result);
        //反转
        for (int i = result.size() - 1; i >= 0; i--) {
            reverse.add(result.get(i));
        }
        return reverse;
    }

    public void levelOrderBottom(TreeNode root, List<List<Integer>> lists) {
        //树,深度
        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
        stack.push(new Pair<>(root, 0));
        int deep = -263849;
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> checkTree = stack.pop();
            deep = checkTree.getValue();
            if (deep == lists.size()) {
                //加元素
                List<Integer> treeData = new ArrayList<>();
                lists.add(treeData);
            }
            //当前结点值加入lists
            lists.get(deep).add(checkTree.getKey().val);
            if (checkTree.getKey().left == null && checkTree.getKey().right == null) {
                continue;
            }
            //深度带入
            ++deep;
            if (checkTree.getKey().left == null) {
                stack.push(new Pair<>(checkTree.getKey().right, deep));
            } else if (checkTree.getKey().right == null) {
                stack.push(new Pair<>(checkTree.getKey().left, deep));
            } else {
                stack.push(new Pair<>(checkTree.getKey().right, deep));
                stack.push(new Pair<>(checkTree.getKey().left, deep));
            }



        }

    }
}



    //public List<List<Integer>> levelOrderBottom(TreeNode root) {
    //    if (root == null) {
    //        return new ArrayList<List<Integer>>();
    //    }
    //    //递归
    //    List<List<Integer>> result = new ArrayList<>();
    //    List<Integer> head = new ArrayList<>();
    //    //把头扔进去
    //    head.add(root.val);
    //    result.add(head);
    //    levelOrderBottom(root, 1, result);
    //    //移除空
    //    result.remove(result.size() - 1);
    //    //反转回
    //    List<List<Integer>> reverse = new ArrayList<>();
    //    for (int i = result.size() - 1; i >= 0; i--) {
    //        reverse.add(result.get(i));
    //    }
    //    return reverse;
    //}
    //
    //
    ////对lists进行初始化,形成自顶向下(root的左右子树不包含root)开始遍历
    ////lists最后一个元素一定是空
    //public void levelOrderBottom(TreeNode root, int deep, List<List<Integer>> lists) {
    //    if (root == null) {
    //        return;
    //    }
    //
    //    //当深度=lists长度
    //    if (deep == lists.size()) {
    //        List<Integer> treeData = new ArrayList<>();
    //        lists.add(treeData);
    //    }
    //
    //    if (root.left == null && root.right == null) {
    //        return;
    //    }else {
    //        //处理当前深度情况
    //        if (root.left != null) {
    //            lists.get(deep).add(root.left.val);
    //        }
    //        if (root.right != null) {
    //            lists.get(deep).add(root.right.val);
    //        }
    //        deep++;
    //    }
    //    levelOrderBottom(root.left, deep, lists);
    //    levelOrderBottom(root.right, deep, lists);
    //}